Introduction:
A digital image or “bitmap” consists of a grid of dots or “pixels” with each pixel defined by a numeric value that gives its color. The number of different colors in a digital image is given by the number of bits assigned to each pixel. The common “color resolutions” are 1 bit per pixel for solid black-and-white nonrealistic images, 8 bits per pixel for grayscale images, nonrealistic color images and coarse realistic images, 24 bits per pixel for “photographic quality” of realistic images and 48 bits per pixel is used for ultrahigh quality images.
An image stored in an uncompressed file format, such as the popular BMP format, usually occupies huge memory space. An image with a pixel resolution of 640 by 480 pixels and 24-bit color resolution will take up 640*480*24/8=921,600 bytes in an uncompressed format. Therefore compression of still image files has become a necessity. The increased use of digitized images, particularly on the Internet, has led to the need to compress such images to allow economical storage and fast data transfer.
In the field of digital image compression, many different techniques have been utilized, such as the JPEG (Joint Photographic Experts Group) standard, Wavelet Transform Compression, Fractal Image Compression, Vector Quantization and the like. In particular, the method known as JPEG and the recent update known as JPEG2000 have become industry standards.
In the basic JPEG method, an image is transformed into a luminance/chrominance color representation conventionally denoted as YUV or YCbCr, where Y is a primary color or luminance component and U and V or Cb and Cr are secondary color components. By averaging together groups of pixels, the number of secondary components stored is reduced. The pixel values for each component are grouped into blocks and each block is transformed by a discrete cosine transform (DCT). In each block, the resulting DCT coefficients are quantized, that is divided by a predetermined quantization coefficient and rounded to integers. The quantized coefficients are encoded based on conditional probability by Huffman or arithmetic coding algorithms known in the art. A normal interchange JPEG file includes the compression parameters, including the quantization tables and encoding tables, in the file headers so a decompression program can reverse the process. The major problems in JPEG compression include a moderate compression ratio, a block effect, and poor progressive image quality.
JPEG 2000 standard is designed to overcome some of the drawbacks of JPEG standard. JPEG2000 standard is an ISO/IEC standard (ISO/IEC 15444-1:2004) for efficient image compression of digital images. In JPEG 2000 standard, the whole image is divided into one or more image tile components; each of these image tile components are then 2-D discrete wavelet transformed using 2-D discrete wavelet transformation. The transform coefficients of each image tile component are then grouped into sub-bands, these sub-bands are further partitioned into rectangular code blocks, and each code block is entropy encoded.
The uncompressed RAW image, which is input sample data, is fed to a pre-processor. The pre-processor block has an encoder. The encoder transforms the range of the input sample data to a nominal dynamic range so that it is approximately centered about zero. If the input sample data is +/−, then it is assumed they are centered at zero. Otherwise, the absolute sample values in each component are level shifted (DC offset) by subtracting a fixed value from each sample to make its value symmetric around zero. Then the discrete wavelet transform (DWT) is applied in each tile to decompose it into a number of wavelet sub-bands at different levels and resolutions.
DWT is an important process to generate resolution-scalable bit streams and decompose the spatial correlation. The output of this stage is a set of transformed coefficients. These transformed coefficients are then quantized. Quantization is used only in lossy compression. The wavelet coefficients in each sub-band are scalar quantized. The quantization step size is calculated based on the dynamic range of the sub band values and constants defined in the standard. The purpose of quantization is to reduce the precision of the sub band coefficients so that fewer bits will be needed to encode the transformed coefficients.
The encoding phase is divided into two steps Tier-1 and Tier-2 coding. The Tier-1 coding is responsible for compressing the coefficient data into a byte stream. The Tier-2 coding consists of Rate Control and Packeting, which is responsible for trimming and organizing this byte stream into a JPEG2000 compliant File format.
Rate control is an important feature provided by JPEG2000 standard. This feature allows an encoder to compress a given image file to a specified target file size, ensuring that this size limit is not exceeded and maximum visual information is packed within. This requires computation of what information is more important visually and what is less, what is to be included in the given file size and what is to be truncated.
The standard rate control scheme used in JPEG2000 calculates the slope as below:RD Slope=(22b×Rlvl—synw2×Band—synw2×NMSE—redc)/ΔR Where,                RD Slope: is the ratio of Distortion and rate        b: is the bit plane number to which the current truncation point belongs        R1v1_synw: is a value of synthesis weight for the selected wavelet filter depending on the current resolution level to which the code block belongs.        Band_synw: is a value of synthesis weight for the selected wavelet filter depending on the current sub-band to which the code block belongs.        NMSE_redc: is a coefficient value computed based on information content in each coding pass and gives an estimate of mean squared error that would result if this coding pass is not included.        ΔR: is the difference in byte count from previous truncation point of code block up to current truncation point for the code block.        
One can see that the computation required to calculate the slope using this suggestive technique is quite complex and would require a lot of computation resource and time to implement in hardware.
This RD slope computation is followed by the Newton-Raphson iterative method to find the best-fit element. All the elements are sorted based on their slopes and then checked if including half of them exceeds the specified limit or not. If it does, then one fourth of these elements are taken and same check is performed, else three fourth of these elements are taken and the check is performed. This process is repeated until it finds the best fit. This computation is called Rate-Distortion Analysis and is handled in the last stage of the encoder namely packeting.
Tier-2 coder operates on the compressed information of every block to arrange their contributions in each quality layer, in a process referred to as packetization. Packeting involves assembling of the final Code-stream in a standard defined file format, which complies with any standard JPEG2000 qualified decoder.
Conventionally, rate distortion is computed for all independent data blocks. It then uses an iterative method for computing a threshold and including the required information and checking for the target file size limit. The disadvantage of this method is that it drastically increases the computation effort and the time required, thereby making it almost impossible for hardware implementation.
An object of the present invention is to overcome the disadvantages of conventional method of digital image compression described before.
Another object of this invention is to provide a simplified formula for the computation of the RD slope.
Another object of this invention is to provide a non-iterative, computationally efficient and hardware friendly system for rate allocation for digital image compression.
Another object of this invention is to reduce the time required for digital image compression.